home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 10 / AACD 10.iso / AACD / Programming / MiniGL / src / hclip.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-04-11  |  14.5 KB  |  496 lines
  1. /*
  2.  * $Id: hclip.c,v 1.1.1.1 2000/04/07 19:44:51 hfrieden Exp $
  3.  *
  4.  * $Date: 2000/04/07 19:44:51 $
  5.  * $Revision: 1.1.1.1 $
  6.  *
  7.  * (C) 1999 by Hyperion
  8.  * All rights reserved
  9.  *
  10.  * This file is part of the MiniGL library project
  11.  * See the file Licence.txt for more details
  12.  *
  13.  */
  14.  
  15. static char rcsid[] = "$Id: hclip.c,v 1.1.1.1 2000/04/07 19:44:51 hfrieden Exp $";
  16.  
  17. #include "sysinc.h"
  18. #include <math.h>
  19.  
  20. #define DUMP_VERTEX(vert) \
  21.  mykprintf("x:%6.3f y:%6.3f z:%6.3f w:%6.3f\nR:%6.3f G:%6.3f B:%6.3f A:%6.3f\nU:%6.3f V:%6.3f\noutcode=0x%X\n",\
  22.          (vert).bx, (vert).by, (vert).bz, (vert).bw,                                                                                      \
  23.          (vert).v.color.r, (vert).v.color.g, (vert).v.color.b, (vert).v.color.a,                                                          \
  24.          (vert).v.u, (vert).v.v, (vert).outcode)
  25.  
  26.  
  27. #define LERP(t,a,b) \
  28.     (a) + (float)t * ( (b) - (a) )
  29.  
  30. #define INTERPOLATE(res,t,a,b) \
  31.     res->bx = LERP(t,a->bx, b->bx); \
  32.     res->by = LERP(t,a->by, b->by); \
  33.     res->bz = LERP(t,a->bz, b->bz); \
  34.     res->bw = LERP(t,a->bw, b->bw); \
  35.     res->v.color.a = LERP(t,a->v.color.a, b->v.color.a); \
  36.     res->v.color.r = LERP(t,a->v.color.r, b->v.color.r); \
  37.     res->v.color.g = LERP(t,a->v.color.g, b->v.color.g); \
  38.     res->v.color.b = LERP(t,a->v.color.b, b->v.color.b); \
  39.     res->v.u = LERP(t,a->v.u, b->v.u); \
  40.     res->v.v = LERP(t,a->v.v, b->v.v);
  41.  
  42. #define CLIP_EPS (1e-7)
  43.  
  44. void hc_CodePoint(MGLVertex *v)
  45. {
  46.     float w = v->bw;
  47.     v->outcode = 0;
  48.  
  49.     if (v->bw < CLIP_EPS )
  50.     {
  51.         v->outcode |= MGL_CLIP_NEGW;
  52.     }
  53.  
  54.     if (-w > v->bx)
  55.     {
  56.         v->outcode |= MGL_CLIP_LEFT;
  57.     }
  58.     else
  59.     if (v->bx > w)
  60.     {
  61.         v->outcode |= MGL_CLIP_RIGHT;
  62.     }
  63.  
  64.     if (-w > v->by)
  65.     {
  66.         v->outcode |= MGL_CLIP_BOTTOM;
  67.     }
  68.     else
  69.     if (v->by > w)
  70.     {
  71.         v->outcode |= MGL_CLIP_TOP;
  72.     }
  73.  
  74.     if (-w > v->bz)
  75.     {
  76.         v->outcode |= MGL_CLIP_BACK;
  77.     }
  78.     else
  79.     if (v->bz > w)
  80.     {
  81.         v->outcode |= MGL_CLIP_FRONT;
  82.     }
  83. }
  84.  
  85. #define x1 (a->bx)
  86. #define y1 (a->by)
  87. #define z1 (a->bz)
  88. #define w1 (a->bw)
  89.  
  90. #define x2 (b->bx)
  91. #define y2 (b->by)
  92. #define z2 (b->bz)
  93. #define w2 (b->bw)
  94.  
  95. #ifdef GLNDEBUG
  96. #define DEBUG_CLIP(name,code) code
  97. #else
  98. #define DEBUG_CLIP(name,code) \
  99.     mykprintf("%s: t=%f\n", #name, t);\
  100.     DUMP_VERTEX(*a); \
  101.     DUMP_VERTEX(*b); \
  102.     code             \
  103.     DUMP_VERTEX(*r);
  104. #endif
  105.  
  106. static void hc_ClipWZero(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  107. {
  108.     float t = (CLIP_EPS-w1)/(w2-w1);
  109.     r->bx = LERP(t,a->bx, b->bx);
  110.     r->by = LERP(t,a->by, b->by);
  111.     r->bz = LERP(t,a->bz, b->bz);
  112.     r->bw = CLIP_EPS;
  113.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  114.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  115.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  116.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  117.     r->v.u = LERP(t,a->v.u, b->v.u);
  118.     r->v.v = LERP(t,a->v.v, b->v.v);
  119.     hc_CodePoint(r);
  120. }
  121.  
  122. static void hc_ClipTop(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  123. {
  124.     float t = (w1-y1)/((w1-y1)-(w2-y2));
  125.     r->bx = LERP(t,a->bx, b->bx);
  126.     r->bz = LERP(t,a->bz, b->bz);
  127.     r->bw = LERP(t,a->bw, b->bw);
  128.     r->by = r->bw;
  129.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  130.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  131.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  132.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  133.     r->v.u = LERP(t,a->v.u, b->v.u);
  134.     r->v.v = LERP(t,a->v.v, b->v.v);
  135.     hc_CodePoint(r);
  136. }
  137.  
  138. static void hc_ClipBottom(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  139. {
  140.     float t = (w1+y1)/((w1+y1)-(w2+y2));
  141.     r->bx = LERP(t,a->bx, b->bx);
  142.     r->bz = LERP(t,a->bz, b->bz);
  143.     r->bw = LERP(t,a->bw, b->bw);
  144.     r->by = -r->bw;
  145.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  146.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  147.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  148.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  149.     r->v.u = LERP(t,a->v.u, b->v.u);
  150.     r->v.v = LERP(t,a->v.v, b->v.v);
  151.     hc_CodePoint(r);
  152. }
  153.  
  154. static void hc_ClipLeft(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  155. {
  156.     float t = (w1+x1)/((w1+x1)-(w2+x2));
  157.     r->by = LERP(t,a->by, b->by);
  158.     r->bz = LERP(t,a->bz, b->bz);
  159.     r->bw = LERP(t,a->bw, b->bw);
  160.     r->bx = -r->bw;
  161.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  162.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  163.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  164.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  165.     r->v.u = LERP(t,a->v.u, b->v.u);
  166.     r->v.v = LERP(t,a->v.v, b->v.v);
  167.     hc_CodePoint(r);
  168. }
  169.  
  170. static void hc_ClipRight(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  171. {
  172.     float t = (w1-x1)/((w1-x1)-(w2-x2));
  173.     r->by = LERP(t,a->by, b->by);
  174.     r->bz = LERP(t,a->bz, b->bz);
  175.     r->bw = LERP(t,a->bw, b->bw);
  176.     r->bx = r->bw;
  177.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  178.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  179.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  180.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  181.     r->v.u = LERP(t,a->v.u, b->v.u);
  182.     r->v.v = LERP(t,a->v.v, b->v.v);
  183.     hc_CodePoint(r);
  184. }
  185.  
  186. static void hc_ClipFront(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  187. {
  188.     float t = (w1-z1)/((w1-z1)-(w2-z2));
  189.     r->bx = LERP(t,a->bx, b->bx);
  190.     r->by = LERP(t,a->by, b->by);
  191.     r->bw = LERP(t,a->bw, b->bw);
  192.     r->bz = r->bw;
  193.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  194.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  195.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  196.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  197.     r->v.u = LERP(t,a->v.u, b->v.u);
  198.     r->v.v = LERP(t,a->v.v, b->v.v);
  199.     hc_CodePoint(r);
  200. }
  201.  
  202. static void hc_ClipBack(MGLVertex *a, MGLVertex *b, MGLVertex *r)
  203. {
  204.     float t = (w1+z1)/((w1+z1)-(w2+z2));
  205.     r->bx = LERP(t,a->bx, b->bx);
  206.     r->by = LERP(t,a->by, b->by);
  207.     r->bw = LERP(t,a->bw, b->bw);
  208.     r->bz = -r->bw;
  209.     r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
  210.     r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
  211.     r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
  212.     r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
  213.     r->v.u = LERP(t,a->v.u, b->v.u);
  214.     r->v.v = LERP(t,a->v.v, b->v.v);
  215.     hc_CodePoint(r);
  216. }
  217.  
  218. #undef x1
  219. #undef y1
  220. #undef z1
  221. #undef w1
  222. #undef x2
  223. #undef y2
  224. #undef z2
  225. #undef w2
  226.  
  227. GLboolean hc_DecideFrontface(GLcontext context, MGLVertex *a, MGLVertex *b, MGLVertex *c, GLubyte outcode)
  228. {
  229.     GLboolean front;
  230.     float a1,a2,b1,b2,r;
  231.     float aw,bw,cw;
  232.  
  233.     if (context->CullFace_State == GL_FALSE) return GL_TRUE;
  234.     if (context->CurrentCullFace == GL_FRONT_AND_BACK) return GL_FALSE;
  235.  
  236.     /*
  237.     ** The following line returns GL_TRUE if one or more of the vertices lie beyond the
  238.     ** camera plane. This is of course a wrong assumption, but those will be culled at
  239.     ** the clipping stage after the negative W coordinates have been removed.
  240.     */
  241.     if (outcode&MGL_CLIP_NEGW) return GL_TRUE;
  242.  
  243.     aw = 1.0 / a->bw;
  244.     bw = 1.0 / b->bw;
  245.     cw = 1.0 / c->bw;
  246.  
  247.     #define EPSILON 1e-5
  248.  
  249.     a1 = a->bx*aw - b->bx*bw;
  250.     a2 = a->by*aw - b->by*bw;
  251.     b1 = c->bx*cw - b->bx*bw;
  252.     b2 = c->by*cw - b->by*bw;
  253.     r  = a1*b2-a2*b1;
  254.  
  255.     if (fabs(a1) < EPSILON && fabs(a2) < EPSILON)
  256.     {
  257.         return GL_TRUE;
  258.     }
  259.  
  260.     if (fabs(b1) < EPSILON && fabs(b2) < EPSILON)
  261.     {
  262.         return GL_TRUE;
  263.     }
  264.  
  265.  
  266.     if ((r < 0.0 && context->CurrentFrontFace == GL_CCW) ||
  267.         (r > 0.0 && context->CurrentFrontFace == GL_CW))
  268.     {
  269.         front = GL_TRUE;
  270.     }
  271.     else
  272.     {
  273.         front = GL_FALSE;
  274.     }
  275.  
  276.     if (context->CurrentCullFace == GL_BACK)
  277.     {
  278.         return front;
  279.     }
  280.     else
  281.     {
  282.         return !front;
  283.     }
  284. }
  285.  
  286. void GLFrontFace(GLcontext context, GLenum mode)
  287. {
  288.     if (mode == GL_CW || mode == GL_CCW)
  289.     {
  290.         context->CurrentFrontFace = mode;
  291.     }
  292.     else
  293.     {
  294.         GLFlagError(context, 1, GL_INVALID_ENUM);
  295.     }
  296. }
  297.  
  298. void GLCullFace(GLcontext context, GLenum mode)
  299. {
  300.     if (mode == GL_FRONT || mode == GL_FRONT_AND_BACK || mode == GL_BACK)
  301.     {
  302.         context->CurrentCullFace = mode;
  303.     }
  304.     else
  305.     {
  306.         GLFlagError(context, 1, GL_INVALID_ENUM);
  307.     }
  308. }
  309.  
  310. /*
  311. ** Complicated clipping macro stuff.
  312. */
  313.  
  314. #define VERTP(i) &(context->VertexBuffer[a->verts[i]])
  315. #define VERT(i) context->VertexBuffer[a->verts[i]]
  316. #define POLYSWAP \
  317.     if (b->numverts == 0) return; \
  318.     temp=a; a=b; b=temp; \
  319.  
  320. #define DOCLIP(edge, routine)                                           \
  321.     if (or_codes & edge)                                                 \
  322.     {                                                                     \
  323.         b->numverts = 0;                                                   \
  324.         prev = a->numverts-1;                                               \
  325.         for (i=0; i<a->numverts; i++)                                        \
  326.         {                                                                     \
  327.             /* Case 1 and 4*/                                                  \
  328.             if (!(VERT(prev).outcode & edge))                                   \
  329.             {                                                                    \
  330.                 b->verts[b->numverts] = a->verts[prev];                           \
  331.                 b->numverts++;                                                     \
  332.             }                                                                       \
  333.             /* Case 3 and 4 */                                                       \
  334.             if ((VERT(prev).outcode ^ VERT(i).outcode) & edge)                        \
  335.             {                                                                          \
  336.                 hc_##routine (VERTP(prev), VERTP(i), &(context->VertexBuffer[free]));   \
  337.                 b->verts[b->numverts]=free++;                                            \
  338.                 b->numverts++;                                                            \
  339.             }                                                                              \
  340.             prev = i;                                                                       \
  341.         }                                                                                    \
  342.         POLYSWAP                                                                              \
  343.     }                                                                                          \
  344.  
  345.  
  346. extern void dh_DrawPoly(GLcontext context, MGLPolygon *poly);
  347. extern void dh_DrawPolyFF(GLcontext context, MGLPolygon *poly);
  348.  
  349. #ifndef GLNDEBUG
  350. void hc_DumpPolygon(GLcontext context, MGLPolygon *poly, char *string, int clipcode)
  351. {
  352.     int i;
  353.     mykprintf("--- %s (0x%X) -- (%d vertices)\n", string,clipcode, poly->numverts);
  354.     for (i=0; i<poly->numverts; i++)
  355.     {
  356.         DUMP_VERTEX(context->VertexBuffer[poly->verts[i]]);
  357.     }
  358.     mykprintf("-------------------------\n");
  359. }
  360.  
  361. #define CLIPDBG(string,code) \
  362.     hc_DumpPolygon(context,a,#string,code);
  363.  
  364. #else
  365.  
  366. #define CLIPDBG(string,code)
  367.  
  368. #endif
  369.  
  370.  
  371. void hc_ClipAndDrawPoly(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
  372. {
  373.     /*
  374.     ** Sutherland-Hodgeman clipping algorithm (almost)
  375.     **
  376.     ** This clipping algorithm sucessively clips against each of the six
  377.     ** clipping planes (additional client-defined clipping planes would
  378.     ** be possible, those would be added to the back of this).
  379.     ** Vertices are copied from a to b and swapped at the end.
  380.     ** Output occurs within the clipping region:
  381.     **
  382.     **                | b
  383.     **               i|/|
  384.     **               /| |
  385.     **              / | |c
  386.     **            a/  |/
  387.     **             | /|j
  388.     **             |/ |
  389.     **            d/  |
  390.     **                |clip plane
  391.     **
  392.     ** In the above figure, the algorithm first consideres edge d-a. Since it
  393.     ** does not cross the clipping plane, it outputs d and proceeds to edge
  394.     ** a-b. Since it crosses, it outputs a, calculates intersection i and outputs it.
  395.     ** No output occurs while b-c is considered, since it lies outside the frustum
  396.     ** and does not cross it. Finally, edge c-d yields output j.
  397.     **
  398.     ** The result is d-a-i-j
  399.     **
  400.     ** Classification of edges are divided into four cases:
  401.     ** Case 1: Edge is completely inside -> two vertices
  402.     ** Case 2: Edge is completely outside -> no output
  403.     ** Case 3: Edge enters the frustum -> one output
  404.     ** Case 4: Edge leaves frustum -> two outputs
  405.     **
  406.     ** At any stage, if the output polygon has zero vertices, return immediately.
  407.     */
  408.  
  409.     MGLPolygon output;
  410.     MGLPolygon *a, *b, *temp;
  411.     int i,j;
  412.     int prev;
  413.     int free = context->VertexBufferPointer;
  414.     GLboolean flag;
  415.     GLubyte original_or_codes = or_codes;
  416.  
  417.     a = poly; b=&output;
  418.  
  419.     CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
  420.     DOCLIP(MGL_CLIP_NEGW, ClipWZero);
  421.  
  422.     for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;
  423.  
  424.     CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
  425.     DOCLIP(MGL_CLIP_LEFT, ClipLeft)
  426.  
  427.     CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
  428.     DOCLIP(MGL_CLIP_RIGHT, ClipRight)
  429.  
  430.     CLIPDBG(ClipFront, MGL_CLIP_FRONT)
  431.     DOCLIP(MGL_CLIP_FRONT, ClipFront)
  432.  
  433.     CLIPDBG(ClipBack, MGL_CLIP_BACK)
  434.     DOCLIP(MGL_CLIP_BACK, ClipBack)
  435.  
  436.     CLIPDBG(ClipTop, MGL_CLIP_TOP)
  437.     DOCLIP(MGL_CLIP_TOP, ClipTop)
  438.  
  439.     CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
  440.     DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)
  441.  
  442.     CLIPDBG(Final,0)
  443.     if ((original_or_codes & MGL_CLIP_NEGW) && a->numverts>2)
  444.     {
  445.         flag = hc_DecideFrontface(context,
  446.             &(context->VertexBuffer[a->verts[0]]),
  447.             &(context->VertexBuffer[a->verts[1]]),
  448.             &(context->VertexBuffer[a->verts[2]]), 0);
  449.         if (flag == GL_FALSE)
  450.             return;
  451.     }
  452.  
  453.     // If we get here, there are vertices left...
  454.     dh_DrawPoly(context, a);
  455. }
  456.  
  457. void hc_ClipAndDrawPolyFF(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
  458. {
  459.     MGLPolygon output;
  460.     MGLPolygon *a, *b, *temp;
  461.     int i,j;
  462.     int prev;
  463.     int free = context->VertexBufferPointer;
  464.  
  465.     a = poly; b=&output;
  466.  
  467.     CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
  468.     DOCLIP(MGL_CLIP_NEGW, ClipWZero);
  469.  
  470.     for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;
  471.  
  472.     CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
  473.     DOCLIP(MGL_CLIP_LEFT, ClipLeft)
  474.  
  475.     CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
  476.     DOCLIP(MGL_CLIP_RIGHT, ClipRight)
  477.  
  478.     CLIPDBG(ClipFront, MGL_CLIP_FRONT)
  479.     DOCLIP(MGL_CLIP_FRONT, ClipFront)
  480.  
  481.     CLIPDBG(ClipBack, MGL_CLIP_BACK)
  482.     DOCLIP(MGL_CLIP_BACK, ClipBack)
  483.  
  484.     CLIPDBG(ClipTop, MGL_CLIP_TOP)
  485.     DOCLIP(MGL_CLIP_TOP, ClipTop)
  486.  
  487.     CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
  488.     DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)
  489.  
  490.     CLIPDBG(Final,0)
  491.  
  492.     // If we get here, there are vertices left...
  493.     dh_DrawPolyFF(context, a);
  494. }
  495.  
  496.